Suffix Array: What is a Suffix Array? A Powerful Tool for Solving String Problems
Suffix array is an array that stores the starting positions of suffixes sorted lexicographically. A suffix is a substring starting from each position in the string to the end (e.g., for "banana", the suffixes are "banana", "anana", etc.). The lexicographical comparison rule is: compare the first different character by its size; if the characters are the same, compare subsequent characters in order; if one suffix is a prefix of the other, the shorter one is considered smaller. Taking "abrac" as an example, the sorted suffix starting positions array is [0, 3, 4, 1, 2] (e.g., the suffix starting at position 0 "abrac" is less than the one at position 3 "ac", and they are arranged in this order). The core value of suffix arrays lies in efficiently solving string problems: by leveraging the close relationship (long common prefix length) between adjacent suffixes after sorting, it can quickly handle tasks such as finding the longest repeated substring and verifying substring existence. For example, the LCP array can be used to find the longest repeated substring, or binary search can verify if a substring exists. In summary, the suffix array provides an efficient solution for string problems by sorting suffix starting positions and is a practical tool for string processing.
Read MoreC++ String Type Basics: String Operations and Common Methods
The C++ string class is a core tool for handling strings, safer and more user-friendly than C-style character arrays, avoiding memory management issues. It requires including the `<string>` header and using the `std` namespace. **Definition and Initialization**: Strings can be directly assigned (e.g., `string s = "Hello"`), constructed via constructor (e.g., `string s3("World")`, `string s4(5, 'A')`), or initialized as empty strings. **Basic Operations**: `size()`/`length()` retrieve the length (return `size_t`). Characters can be accessed with `[]` (unboundsafe) or `at()` (boundsafe). Concatenation is done via `+`, `+=`, or `append()`. **Common Methods**: `find()` searches for substrings (returns position or `npos`), `replace()`, `insert()`, `erase()`, `compare()`, and `clear()` (empties the string). **Conversion**: Convert `string` to `const char*` with `c_str()`, and `const char*` to `string` via direct construction or assignment. **Notes**: Avoid mixing C string functions. `size_t` is unsigned (watch for comparisons with negative values), and `empty()` checks for empty strings. (Word count: ~190)
Read More